
//Problem:Sort a linked list using insertion sort.

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
    	ListNode *new_head; //new_head points increasing sorted linked list
    	new_head = (ListNode *)malloc(sizeof(ListNode));
    	if(head ==NULL)
    		return head;



    	new_head->next =NULL; // We need  to create a new list, if not, there will be circle
    	new_head->val = head->val;


    	if(head->next == NULL)// Easy to ignore the extrem case
    		return head;

    	ListNode *p = head->next;
    	ListNode *nx;
    	//Iterate all the elements in the linked list
    	while(p !=NULL){
    		if(p->val < new_head->val){
    			nx = p->next;
    			p->next = new_head;
    			new_head = p;

    			p = nx;
    			continue;
    		}
    		ListNode *now, *prev;
    		prev = new_head;
    		now  = new_head->next;
    		while(now !=NULL and p->val > now->val){
    			prev = now;
    			now = now->next;
    		}
    		//Insert p before now and after prev
    		nx=p->next;
    		prev->next = p;
    		p->next = now;

    		p = nx;

    	}

    	return new_head;
    	//Test
    	/*
    	ListNode *new_p = new_head;
		while(new_p !=NULL){
			fprintf(stdout,"%d ", new_p->val);
			new_p =new_p->next;
		}*/

    }
};